Leetcode-Valid Parentheses

发表于 | 分类于 |

Valid Parentheses

验证有效括号对：给定一个只包含括号类型的字符串，判断该字符串的括号是否有效闭合。Description
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

解题思路：
采用栈来解决，依次检查给的characters，如果是左括号都入栈；如果是右括号，检查栈如果为空，证明不能匹配，如果栈不空，弹出top，与当前扫描的括号检查是否匹配。全部字符都检查完了以后，判断栈是否为空，空则正确都匹配，不空则证明有没匹配的。

代码中采用字典方式，将右括号作为键，将左括号作为值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    stack = []
    dict = {')':'(', ']':'[', '}':'{'}
    
    for char in s:
        if char in dict.values():
            stack.append(char)
        elif char in dict.keys():
            if stack==[] or stack.pop()!=dict[char]:
                return False
        else:
            return False
    
    return stack==[]